#include <iostream>
#include <vector>
using namespace std;

void merge(int *p, int l, int mid, int r) {
  int *q = new int[r - l + 1];
  int lc = l;
  int rc = mid + 1;
  int count = 0;
  while (lc <= mid && rc <= r) {
    if (p[lc] <= p[rc]) {
      q[count] = p[lc];
      ++lc;
    } else {
      q[count] = p[rc];
      ++rc;
    }
    ++count;
  }
  while (lc <= mid) {
    q[count] = p[lc];
    ++lc;
    ++count;
  }
  while (rc <= r) {
    q[count] = p[rc];
    ++rc;
    ++count;
  }
  for (int i = 0; i < count; ++i) {
    p[l + i] = q[i];
  }
}

void mergesort(int *p, int l, int r) {
  if (l >= r) {
    return;
  }
  int mid = l + ((r - l) >> 1);
  mergesort(p, l, mid);
  mergesort(p, mid + 1, r);
  merge(p, l, mid, r);
}

void mergesort2(int *nums, int l, int r) {
  int len = r - l + 1;
  int k = 1;
  while (k < len) {
    int tl = l;
    while (tl <= r) {
      int tm = tl + k - 1;
      if (tm > r) {
        break;
      }
      int tr = min(tm + k, r);
      merge(nums, tl, tm, tr);
      tl = tr + 1;
    }
    // 防止数字特别大的时候k * 2溢出
    if (k > len / 2) {
      break;
    }
    k = k * 2;
  }
}

int main() {
  int a[] = {5, 4, 3, 2, 1};
  mergesort2(a, 0, 4);
  for (int i = 0; i < 5; ++i) {
    cout << a[i] << " ";
  }
  cout << endl;
}
